package tree.leetcode_538_medium;

public class MorrisSolution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        //反向中序遍历，莫里斯遍历。
        //正向是 如果左孩子存在，找左孩子的最右边节点； 那么反向就是如果右孩子存在，找右孩子的最左边节点
        TreeNode cur = root;
        int sum = 0;
        while (cur != null) {
            TreeNode mostRight = cur.right;
            if (mostRight != null) {
                //找右孩子的最左
                while (mostRight.left != null && mostRight.left != cur) {
                    mostRight = mostRight.left;
                }
                if (mostRight.left == null) {
                    mostRight.left = cur;
                    cur = cur.right;
                } else {
                    //中序遍历是第二次回到节点时 做事
                    sum += cur.val;
                    cur.val = sum;
                    mostRight.left = null;
                    cur = cur.left;
                }
            } else {
                sum += cur.val;
                cur.val = sum;
                cur = cur.left;
            }
        }
        return root;
    }
}
